import re
import fileinput
import pygraphviz as pgv

pattern = re.compile("(?!')([a-z][a-z_0-9]*)(?![a-z_0-9]*')")

input_file = "in_grammar.txt"
output_file = "out_grammar.txt"
root = 'file_input'
exclude_list = ['listmaker']
print_tree = True
print_graph = False

class Production:
    """Represents a non terminal symbol"""
    def __init__(self, production):
        self.production = production.strip()
        
        nonterminals = re.findall(pattern, production)
        self.name = nonterminals[0]
        self.dependencies = nonterminals[1:]
        
    def __str__(self):
        return self.production

def build_dependency_tree(productions):
    worklist = ['file_input']
    excludes = set(exclude_list)
    has_excludes = set([])
    result = []
    
    tree=pgv.AGraph()
    
    while len(worklist) > 0:
        current = productions[worklist.pop(0)]
        missing_dependencies = []
        for dependency in current.dependencies:
            
            if dependency in excludes:
                has_excludes.add(current.name)
            elif dependency not in (set(result) | set(worklist)):
                missing_dependencies.append(dependency)
                tree.add_edge(current.name, dependency)
        result.append(current.name)
        worklist = missing_dependencies + worklist
        
    if print_tree:
        tree.draw('tree.png', prog='dot')
    
    if exclude_list and output_file:
        f = open(output_file, 'w')
        for p in result:
            line = productions[p].production + '\n'
            line = '###EXCLUDE### ' + line if p in has_excludes else line
            f.write(line)
        f.close()
    
    
    
def print_dependency_graph(productions):
    graph=pgv.AGraph(strict=False, directed=True)

    for name, prod in productions.items():
        for d in prod.dependencies:
            graph.add_edge(name, d)
    
    graph.draw('graph.png', prog='dot')
    
if __name__ == '__main__':
    productions = {}
    
    for line in fileinput.input(input_file):
        if line.startswith('#') or line.strip() == '': continue
        production = Production(line)
        productions[production.name] = production
    
    build_dependency_tree(productions)
    
    if print_graph:
        print_dependency_graph(productions)